// https://www.lintcode.com/problem/search-in-rotated-sorted-array/

public class Solution {
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    public int search(int[] A, int target) {
        // write your code here
        int start = 0, end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[start] <= A[mid]) {
                if ((A[start] <= target) && (A[mid] > target)) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            else {
                if ((A[end] >= target) && (A[mid] < target)) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}